/* Copyright 2001,2002,2003 NAH6 BV
 * All Rights Reserved
 *
 *  $Header: /var/lib/cvs/secphone/ui/bignum/bignum.cpp,v 1.5 2003/11/21 12:39:24 itsme Exp $
 *
 * This is the implementation of Number, a wrapper class around
 * the GMP library.
 *
 * This class is used to facilitate calculations with large numbers.
 * Used in all diffiehellman calculations.
 *
 *
 */

#ifndef _WIN32_WCE
// this is needed for the win32 desktop version.
#define _X86_
#endif

#include <windows.h>
#include <TCHAR.h>

#include "debug.h"
#include "gmp/gmp.h"        // mpz_*

#include "bignum.h"
//#include "abort.h"
// make sure this and the project using this dll are both compiled
// with the same threading define: '_MT'
// cause: "__default_alloc_template<__thrd,0> " with __thrd depending on _MT
#include <string>
#include "vectorutils.h"
#include "stringutils.h"

// todo: possible optimization:
//    - in operator+() etc, use mpz_add(tmp,this,b) iso using operator +=
//    - change the mpz version to IntNumber

// possible design improvements:
//    - modular functions to ModularNumber class

//    - add RatNumber with mpq version
//    - add RealNumber with mpf version

//    - add Complex<type> with the above.
//    - add Modular<type> with the above.
//
//    - add operator # (int, const Number&)  functions
//

// -----------------------------------------------------------------------------
//
// Note:
//    memory security is provided by the function __gmp_wince_free 
//    in ui/bignum/gmp/memory.cpp, memory is erased there after used.
//#define BYTES_PER_MP_LIMB 4
//void
//mpz_clear (mpz_ptr m)
//{
//  (*__gmp_free_func) (m->_mp_d, m->_mp_alloc * BYTES_PER_MP_LIMB);
//}
//
//void
//mpz_init (mpz_ptr x)
//{
//  x->_mp_alloc = 1;
//  x->_mp_d = (mp_ptr) (*__gmp_allocate_func) (BYTES_PER_MP_LIMB);
//  x->_mp_size = 0;
//
//#ifdef __CHECKER__
//  /* let the low limb look initialized, for the benefit of mpz_get_ui etc */
//  x->_mp_d[0] = 0;
//#endif
//}
//
//void
//mpz_set_ui (mpz_ptr dest, unsigned long int val)
//{
//  mp_size_t size;
//
//  dest->_mp_d[0] = val & GMP_NUMB_MASK;
//  size = val != 0;
//
//#if BITS_PER_ULONG > GMP_NUMB_BITS  /* avoid warnings about shift amount */
//  if (val > GMP_NUMB_MAX)
//    {
//      MPZ_REALLOC (dest, 2);
//      dest->_mp_d[1] = val >> GMP_NUMB_BITS;
//      size = 2;
//    }
//#endif
//
//  dest->_mp_size = size;
//}
int
mpz_cmp_ss (mpz_srcptr u, signed long int v_digit)
{
  mp_size_t usize = u->_mp_size;
  mp_size_t vsize;
  mp_limb_t u_digit;

#if GMP_NAIL_BITS != 0
  /* FIXME.  This isn't very pretty.  */
  mpz_t tmp;
  mp_limb_t tt[2];
  PTR(tmp) = tt;
  ALLOC(tmp) = 2;
  mpz_set_si (tmp, v_digit);
  return mpz_cmp (u, tmp);
#endif

  vsize = 0;
  if (v_digit > 0)
    vsize = 1;
  else if (v_digit < 0)
    {
      vsize = -1;
      v_digit = -v_digit;
    }

  if (usize != vsize)
    return usize - vsize;

  if (usize == 0)
    return 0;

  u_digit = u->_mp_d[0];

  if (u_digit == (mp_limb_t) (unsigned long) v_digit)
    return 0;

  if (u_digit > (mp_limb_t) (unsigned long) v_digit)
    return usize;
  else
    return -usize;
}


Number::Number()
{
    mpz_init(value);
}
Number::Number(const Number& n)
{
    mpz_init_set(value, n.value);
}
Number::Number(int n)
{
    mpz_init_set_si(value, n);
}
Number Number::FromInteger(int n)
{
    Number result;

    mpz_init_set_si(result.value, n);

    return result;
}
int Number::ToInteger() const
{
    return mpz_get_si(value);
}

Number::~Number()
{
    mpz_clear(value);
}

void Number::FromByteVector(const ByteVector& buf)
{
    // 1 : most significant word first
    // 0 : endianness= systemdefault
    // 0 : no nails.
    mpz_import(value, buf.size(), 1, sizeof(BYTE), 0, 0, vectorptr(buf));
}

ByteVector Number::ToByteVector() const
{
    if (*this==0)
        return ByteVector();

    ByteVector result(NrOfBytesInNumber());

    unsigned int len;
    mpz_export(vectorptr(result), &len, 1, sizeof(BYTE), 0, 0, value);

    if (len!=result.size())
        debug("ERROR: ToByteVector expected %d, got %d bytes\n", result.size(), len);

    return result;
}

void Number::setbit(int bitnr)
{
    mpz_setbit(value, bitnr);
}
bool Number::getbit(int bitnr) const
{
    bool bit= mpz_tstbit(value, bitnr)!=0;

    return bit;
}

const Number& Number::operator = (const Number& b)
{
    mpz_set(value, b.value);

    return *this;
}
const Number& Number::operator = (int b)
{
    mpz_set_si(value, b);
    return *this;
}

Number& Number::operator += (const Number& b)
{
    mpz_add(value, value, b.value);
    
    return *this;
}
Number& Number::operator -= (const Number& b)
{
    mpz_sub(value, value, b.value);
    
    return *this;
}
Number& Number::operator *= (const Number& b)
{
    mpz_mul(value, value, b.value);
    
    return *this;
}
Number& Number::operator /= (const Number& b)
{
    mpz_tdiv_q(value, value, b.value);
    
    return *this;
}

Number& Number::operator %= (const Number& b)
{
    mpz_tdiv_r(value, value, b.value);
    
    return *this;
}
Number& Number::operator ^= (const Number& b)
{
    mpz_xor(value, value, b.value);
    
    return *this;
}


Number& Number::operator += (int b)
{
    if (b<0)
        mpz_sub_ui(value, value, (unsigned int)-b);
    else
        mpz_add_ui(value, value, (unsigned int)b);
    
    return *this;
}
Number& Number::operator -= (int b)
{
    if (b<0)
        mpz_add_ui(value, value, (unsigned int)-b);
    else
        mpz_sub_ui(value, value, (unsigned int)b);
    
    return *this;
}
Number& Number::operator *= (int b)
{
    mpz_mul_si(value, value, b);
    
    return *this;
}
Number& Number::operator /= (int b)
{
    if (b<0)
    {
        mpz_tdiv_q_ui(value, value, (unsigned int)-b);
        mpz_neg(value, value);
    }
    else if (b>0)
        mpz_tdiv_q_ui(value, value, (unsigned int)b);
    else
    {
        debug("ERROR: division by 0 attempted\n");
       // abort();
    }

    return *this;
}

Number& Number::operator %= (int b)
{
    if (b<0)
    {
        mpz_tdiv_r_ui(value, value, (unsigned int)-b);
        mpz_sub_ui(value, value, (unsigned int)-b);
    }
    else if (b>0)
        mpz_tdiv_r_ui(value, value, (unsigned int)b);
    else
    {
        debug("ERROR: division by 0 attempted\n");
      //  abort();
    }
    
    return *this;
}
Number& Number::operator ^= (int b)
{
    return *this ^= Number::FromInteger(b);
}

int Number::Compare(const Number& b) const
{
    int cmp= mpz_cmp(value, b.value);

    return cmp;
}
int Number::Compare(int intvalue) const
{
	int aa = mpz_cmp_ss(value, intvalue);
    int cmp= mpz_cmp_si(value, intvalue);

    return cmp;
}

Number Number::ModularPower(const Number& exponent, const Number& modulus) const
{
    Number result;

    mpz_powm(result.value, value, exponent.value, modulus.value);

    return result;
}


std::string Number::AsString(int base /*=10*/) const
{
    std::string str; str.resize(NrOfDecimalDigitsInNumber()+2);
    char *strptr= mpz_get_str(stringptr(str), base, value);

    str.resize(strlen(strptr));
    return str;
}

int Number::NrOfBytesInNumber() const
{
    return mpz_sizeinbase(value, 256);
}
int Number::NrOfBitsInNumber() const
{
    return mpz_sizeinbase(value, 2);
}
int Number::NrOfDecimalDigitsInNumber() const
{

// this causes a crash in libgcc.a, caused by it being compiled for xscale, iso the armv4.
// gcc3.3.1 compiled for the armv4 causes another, unresearched, problem in libgmp.a

//    return mpz_sizeinbase(value, 10);

// so instead I just return a slight overestimate.
    return (NrOfBitsInNumber()*31)/100+1;
}

bool Number::IsPerfectPower() const
{
    return mpz_perfect_power_p(value)!=0;
}

Number Number::SquareRoot() const
{
    Number sqrt;

    mpz_sqrt(sqrt.value, value);

    return sqrt;
}
Number Number::operator - () const
{
    Number tmp;

    mpz_neg(tmp.value, value);
    
    return tmp;
}


// -----------------------------------------------------------------------------
// generic Number code: these do not directly use gmp library functions.
// -----------------------------------------------------------------------------

bool Number::operator == (const Number& b) const
{
    return Compare(b)==0;
}
bool Number::operator != (const Number& b) const
{
    return Compare(b)!=0;
}
bool Number::operator < (const Number& b) const
{
    return Compare(b)<0;
}
bool Number::operator <= (const Number& b) const
{
    return Compare(b)<=0;
}
bool Number::operator > (const Number& b) const
{
    return Compare(b)>0;
}
bool Number::operator >= (const Number& b) const
{
    return Compare(b)>=0;
}

bool Number::operator == (int intvalue) const
{
    return Compare(intvalue)==0;
}
bool Number::operator != (int intvalue) const
{
    return Compare(intvalue)!=0;
}
bool Number::operator < (int intvalue) const
{
    return Compare(intvalue)<0;
}
bool Number::operator <= (int intvalue) const
{
    return Compare(intvalue)<=0;
}
bool Number::operator > (int intvalue) const
{
    return Compare(intvalue)>0;
}
bool Number::operator >= (int intvalue) const
{
    return Compare(intvalue)>=0;
}

int Number::ModularCompare(int b, const Number& modulus) const
{
    Number rem=*this;
    rem -= b;
    rem %= modulus;
    return rem.Compare(0);
}

Number Number::GCD(const Number& b) const
{
    Number nc= *this % b;
    Number na= *this;
    Number nb= b;

    while (nc != 0)
    {
        na= nb;
        nb= nc;
        nc %= nb;
    }
    return nb;
}
/* ----------------------------------------------------------------------------- */
Number Number::operator + (const Number& b) const
{
    Number tmp(*this);
    tmp += b;

    return tmp;
}
Number Number::operator - (const Number& b) const
{
    Number tmp(*this);
    tmp -= b;

    return tmp;
}
Number Number::operator * (const Number& b) const
{
    Number tmp(*this);
    tmp *= b;

    return tmp;
}
Number Number::operator % (const Number& b) const
{
    Number tmp(*this);
    tmp %= b;

    return tmp;
}
Number Number::operator / (const Number& b) const
{
    Number tmp(*this);
    tmp /= b;

    return tmp;
}
Number Number::operator ^ (const Number& b) const
{
    Number tmp(*this);
    tmp ^= b;

    return tmp;
}


Number Number::operator + (int b) const
{
    Number tmp(*this);
    tmp += b;

    return tmp;
}
Number Number::operator - (int b) const
{
    Number tmp(*this);
    tmp -= b;

    return tmp;
}
Number Number::operator * (int b) const
{
    Number tmp(*this);
    tmp *= b;

    return tmp;
}
Number Number::operator % (int b) const
{
    Number tmp(*this);
    tmp %= b;

    return tmp;
}
Number Number::operator / (int b) const
{
    Number tmp(*this);
    tmp /= b;

    return tmp;
}
Number Number::operator ^ (int b) const
{
    Number tmp(*this);
    tmp ^= b;

    return tmp;
}

// ----------------------------------------------------------------------------

// this functions performs some basic tests un the Number class
bool testNumberClass()
{
    Number a(1);
    Number b(2);

// test comparison
    bool bres= (a==b);
    if (bres) debug("1==2\n");
    bres= (a!=b);
    if (!bres) debug("not 1!=2\n");

// test simple arithmetic
    a+=b;
    if (a != 3) debug("1+2 != 3\n");

    if (a < 3) debug("3 < 3\n");
    if (a > 3) debug("3 > 3\n");

    if (! ( a>=3 && a<=3 ) ) debug(" ! 3<=3 && 3>=3 \n");

    a=1234;

    a%= 99;
    if (a != 46) debug("1234 % 99 != 46\n");

    a*= b;

    if (a != 92) debug("46 * 2 != 92\n");

// test bittest function
    if (a.getbit(0) || a.getbit(1) || !a.getbit(2) || !a.getbit(3)
        || !a.getbit(4) || a.getbit(5) || !a.getbit(6))
        debug("92 != B.1011100\n");

// test large number arithmetic
    a=0;
    a.setbit(1024);
    a+=13;

    b=0;
    b.setbit(512);
    b -= 11;

    a %= b;

    if (a != 134) debug("(2^1024+13) mod (2^512-11) != 134\n");

    
    a=0;
    a.setbit(1024);
    a+=13;

    Number m;
    m.setbit(63);
    m-=73;

// test modpower
    Number res= a.ModularPower(b,m);
    //expr(_power(Dom::IntegerMod(2^63-73)(2^1024+13), 2^512-11)) mod 65536 == 5843

    res %= 65536;
    if (res != 5843) debug("expr(_power(Dom::IntegerMod(2^63-73)(2^1024+13), 2^512-11)) mod 65536 != 5843\n");

    a ^= a;

    if (a != 0) debug("a xor a should have resulted in ZERO\n");
// test mod compare

    a=124;
    if (a.ModularCompare(1, Number::FromInteger(123))!=0)
        debug("124 != 1 (mod 123)\n");
    if (a.ModularCompare(-1, Number::FromInteger(125))!=0)
        debug("124 != -1 (mod 125)\n");

// test printing of strings
    a=0;
    a.setbit(1023);
    a -= 1;

    // test im/export of nr.
    
    ByteVector bytenr= a.ToByteVector();
    b.FromByteVector(bytenr);
    if (a!=b)
        debug("number not correctly exported and imported\n");

    StringList list;
    for (int nb=0 ; nb<20 ; ++nb)
    {
        Number nr;
        nr= (1<<nb)-1;

        bytenr= nr.ToByteVector();

        list.push_back(nr.AsString());
    }
    std::string liststring= JoinStringList(list, ", ");
    if (liststring!=std::string("0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, " \
            "4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287"))
    {
        debug("error in stringconversions: %hs\n", liststring.c_str());
    }


    a=123; b=999;
    Number c= a^b+a^(b*2);

    if (c!=983)
        debug(" a^b+a^(b*2) != 983\n");

    // test div+mod
    for (a=Number::FromInteger(-10) ; a < 10 ; a+=1)
    {
        for (b=Number::FromInteger(-10) ; b < 10 ; b += (b==-1)?2:1)
        {
            Number r= a%b;
            Number q= a/b;
            if (q*b+r != a)
            {
                debug("[%hs]*%hs+[%hs] != %hs\n",
                    q.AsString().c_str(), b.AsString().c_str(), r.AsString().c_str(), a.AsString().c_str());
                debug("bignum error\n");
            }
        }
    }

    debug("number class tested\n");

    return true;
}

